/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-15
 * Time: 9:20
 */
//416.分割等和子集
class Solution2 {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) {
            sum += x;
        }

        if(sum % 2 == 1) {
            return false;
        }

        int m = sum / 2;

        //dp[i][j]表示从前i个数所有选法能否凑成j
        boolean[] dp = new boolean[m+1];

        //初始化
        dp[0] = true;

        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= nums[i-1]; j--) { //修改遍历顺序
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[m];
    }
}
